package com.cqs.leetcode;

import com.cqs.leetcode.ds.Trie;

/**
 * Created by cqs on 2018/3/24.
 */
public class LongestCommonPrefix {
    //解法一
    public String longestCommonPrefix(String[] strs) {
        if (strs == null) return null;
        if (strs.length == 0) return strs[0];
        int min = strs[0].length();
        //找出最短的字符串
        for (int i = 1; i < strs.length; i++) {
            min = Math.min(min, strs[i].length());
        }
        //从左到右 挨个遍历
        for (int i = 0; i < min; i++) {
            for (int j = 1; j < strs.length; j++) {
                //相同索引下 出现字符不同 查找结束
                if (strs[j].charAt(i) != strs[0].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0].substring(0, min);
    }


    public String longestCommonPrefix2(String[] strs) {
        //分支思想
        if (strs.length == 0) return "";
        return divide(strs, 0, strs.length - 1);
    }

    //切分
    private String divide(String[] strs, int left, int right) {
        if (left == right) return strs[left];
        int mid = (left + right) / 2;
        String s1 = divide(strs, left, mid);
        String s2 = divide(strs, mid + 1, right);
        return commonPrefix(s1, s2);
    }

    //归并
    private String commonPrefix(String s1, String s2) {
        if (s1 == null || s2 == null) return null;
        int min = Math.min(s1.length(), s2.length());
        for (int i = 0; i < min; i++) {
            if (s1.charAt(i) != s2.charAt(i)) return s1.substring(0, i);
        }
        return s1.substring(0, min);
    }

    public String longestCommonPrefix3(String[] strs) {
        Trie trie = new Trie();
        for (String str : strs) {
            trie.insert(str);
        }

        Trie.Node node = trie.getRoot();
        int len = 0;
        while (node.getChildren().size() == 1) {
            ++len;
            Character key = node.getChildren().keySet().iterator().next();
            node = node.getChildren().get(key);
        }
        return strs[0].substring(0,len);
    }

    public static void main(String[] args) {
        LongestCommonPrefix l = new LongestCommonPrefix();
        String[] data = {"c", "d"};
        System.out.println(l.longestCommonPrefix2(data));
    }
}
